package algorithms.search;

import algorithms.log.Log;
import algorithms.sort.GetRandomArr;
import algorithms.sort.InsertSort;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr(100000);
        InsertSort.insertSort(arr);
        System.out.println(Arrays.toString(arr));
        int target = arr[100];
        System.out.println("target:"+target);
        Log.start();
        int index = binarySearch(arr, target);
        Log.end();
        if(index >= 0)
            System.out.println("target:"+arr[index]+" 下标为:"+index);

//        int[] arr1 = {1,2,2,2,3,3,3,3,4,5,6};
//        int index = binarySearchLeftIndex(arr1, 2);
//        if(index >= 0)
//            System.out.println("target:"+arr1[index]+" 下标为:"+index);

    }


    /**
     * 二分查找
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr,int target) {
        int l = 0; // 左边界
        int r = arr.length -1;// 右边界
        while (l <= r) {
//            int mid = (l+r) / 2;
            /*
            整数溢出的场景‌：
            当数组非常大时，left 和 right 的值可能接近 Integer.MAX_VALUE（例如 2,147,483,647）。
            若直接计算 left + right，二者的和可能超过 Integer.MAX_VALUE，导致结果为负数或错误值（整数溢出）。
             */
            int mid = l + (r - l) / 2;
            if(arr[mid] == target)// 命中条件
                return mid;
            else if(arr[mid] > target)// 目标在左区间
                r = mid -1;
            else if (arr[mid] < target)// 目标在右区间
                l = mid + 1;
        }
        return -1;
    }

    /**
     * 二分查找变体的题目：在有序数组中找某个数的最左/（右）的位置
     *
     * 例：122233334564 问找3最左的下标?
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchLeftIndex(int[] arr,int target) {
        int l = 0; // 左边界
        int r = arr.length -1;// 右边界
        while (l <= r) {
            //int mid = (l+r) / 2;
            int mid = l + (r - l) / 2;
            if(arr[mid] > target)// 目标在左区间
                r = mid -1;
            else if (arr[mid] < target)// 目标在右区间
                l = mid + 1;
            if(arr[mid] == target) {// 找到最左边的下标
                if(mid > l)
                    r = mid - 1;// 区间向左偏移
                else if (mid == l)
                    return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找变体的题目：在无序arr中，满足相邻一定不相等条件，要求查找任意一个局部最小值。
     * 局部最小定义：
     * 	1.对于最左边 :最左边小于相邻与右边的值 如[ 1,2 ....]
     * 	2.对于最右边，最右边小于相邻于左边的值 如[.....2,1]
     * 	3.对于中部第i个位置，满足i小于i-1,i+1的位置上的值 如[....5,3,6....] 第i个位置为3
     * 	要求时间复杂度O(n)
     * 例：
     * @param arr
     * @return
     */
//    public static int binarySearchRangeMin(int[] arr) {
//        int l = 0; // 左边界
//        int r = arr.length -1;// 右边界
//        while (l <= r) {
//            int mid = (l+r) / 2;
//            if(arr[mid] > arr[l])// 中间位置比左边位置大，
//                r = mid -1;
//            else if (arr[mid] < arr[r])// 目标在右区间
//                l = mid + 1;
//            if(arr[mid] == target) {// 找到最左边的下标
//                if(mid > l)
//                    r = mid - 1;// 区间向左偏移
//                else if (mid == l)
//                    return mid;
//            }
//        }
//        return -1;
//    }





}
